5076. Regular graph

 

Undirected graph is called regular, if all its vertices have the same degree.

Graph is given by list of edges. Check, is it regular.

 

Input. First line contains number n (1 ≤ n ≤ 100) of vertices and number m (1 ≤ m ≤ n (n – 1) / 2) of edges in a graph. Then given m pairs of numbers – the edges of graph.

 

Output. Print YES if graph is regular and NO otherwise.

 

Sample input 1

Sample output 1

3 3

1 2

1 3

2 3

YES

 

 

Sample input 2

Sample output 2

3 2

1 2

2 3

NO

 

 

SOLUTION

graphs

 

Algorithm analysis

Find the degree of each vertex of the graph. If all degrees of the vertices of a graph are equal, then the graph is regular, otherwise – no.

 

Example

The graphs given in the samples have the form:

The degrees of all vertices of the first graph equal to 2, so the graph is regular. In the second example, the vertices of the graph have different degrees. Second graph is not regular.

 

Algorithm realization

Count the degrees of vertices in array deg.

 

#define MAX 110

int deg[MAX];

 

Read the input data.

 

scanf("%d %d",&n,&m);

memset(deg,0,sizeof(deg));

for(i = 0; i < m; i++)

{

 

For each undirected edge (a, b) increase by 1 the degrees of vertices a and b.

 

  scanf("%d %d",&a,&b);

  deg[a]++; deg[b]++;

}

 

Check, whether all elements of array deg are equal. If they all are equal (the degrees of all graph vertices are the same), then flag = 0 and graph is regular.

 

flag = 0;

for(i = 1; i < n; i++)

  if (deg[i] != deg[i+1]) flag = 1;

 

Depending on the value of the variable flag, print the answer.

 

if (flag == 0) printf("YES\n");

else printf("NO\n");

 

Java realization

 

import java.util.*;

 

public class Main

{

  public static void main(String[] args) 

  {

    Scanner con = new Scanner(System.in);

    int n = con.nextInt();

    int m = con.nextInt();

    int deg[] = new int[n+1];

   

    for(int i = 0; i < m; i++)

    {

      int a = con.nextInt();

      int b = con.nextInt();

      deg[a]++;

      deg[b]++;

    }

       

    int flag = 0;

    for(int i = 1; i < n; i++)

      if (deg[i] != deg[i+1]) flag = 1;

 

    if (flag == 0) System.out.println("YES");

    else System.out.println("NO");

    con.close();

  }

}